package com.cong.leetcode._29;

import java.util.Stack;
import java.util.Stack;
class Solution {

    public static void main(String[] args) {
        int res = new Solution().divide(-7, 3);
        System.out.println(res);
    }

    public int divide(int dividend, int divisor) {
        System.out.println(Integer.toBinaryString(-2147483648));
        int mask = 1 << 31;
        int flag = ((dividend ^ divisor) & mask) == mask ? -1 : 1;


        if(flag == -1){
            dividend = dividend > 0 ? dividend : -dividend;
            divisor = divisor > 0 ? divisor : - divisor;
        }
        Stack<Integer> granute = new Stack<>();
        Stack<Integer> facs = new Stack<>();
        granute.push(divisor);
        facs.push(1);

        int current = 0;
        int times = 0;
        int dir = 1;

        do {

            int g = granute.peek();
            int f = facs.peek();
            if (current + g == dividend) {
                times += f;
                return flag == 1 ? times : -times;
            }/*found equal*/

            if (current + g > dividend && g == divisor) {
                return flag == 1 ? times : -times;
            }/*found*/

            if (current + g < dividend) {
                current += g;
                times += f;
                if (dir == 1) {
                    granute.push(g << 1);
                    facs.push(f << 1);
                }else {
                    if (g == divisor) {
                        return flag == 1 ? times : -times;
                    }
                    granute.pop();
                    facs.pop();
                }
                continue;
            }/*stack decrease*/

            if(current + g > dividend) {
                dir = -1;
                granute.pop();
                facs.pop();
            }
        }while(granute.size() > 0);
        return -999;


    }

}